// https://www.lintcode.com/problem/find-peak-element/my-submissions

class Solution {
public:
    /**
     * @param A: An integers array.
     * @return: return any of peek positions.
     */
    int findPeak(vector<int> &A) {
        // TLE
        // for (int i = 0; i < A.size(); ++i)
        // {
        //     if (i && A[i] < A[i - 1]) return i - 1;
        // }
        int low = 0;
        int high = A.size() - 1;
        while (low + 1 < high)
        {
            int mid = (high - low) / 2 + low;
            if (A[mid] > A[mid - 1] && A[mid] > A[mid + 1]) return mid;
            if (A[mid] > A[mid - 1]) low = mid;
            else high = mid;
        }
    }
};